/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q2522.java
 * @Author : WangRuoyu
 * @Date 2023/1/10 15:20
 */

package leetcode;

public class Q2522 {
    public int minimumPartition(String s, int k) {
        int res = 0;

        int[] f = new int[100001];

        int index = -1;

        for (int i = 0; i < s.length(); i++) {
            if (Long.parseLong(s.substring(0, i + 1)) <= k) {
                f[i] = 1;
            } else {
                index = i;
                break;
            }
        }

        if (index == -1) {
            return f[s.length() - 1];
        }

        for (int i = index; i < s.length(); i++) {
            String str = s.substring(0, i + 1);
            int tmpres = 100010;
            for (int j = i; j > 0; j--) {
                long tmp = Long.parseLong(str.substring(j, i + 1));
                if (tmp > k) {
                    break;
                } else {
                    tmpres = Math.min(tmpres, f[j - 1] + 1);
                }
            }
            if (tmpres == 100010) {
                return -1;
            }
            f[i] = tmpres;
        }

        return f[s.length() - 1];
    }

    public static void main(String[] args) {
        Q2522 sl = new Q2522();
//        String s = "165462";
//        int k = 60;
        String s = "1";
        int k = 1;
        System.out.println(sl.minimumPartition(s, k));
    }
}